Guess number higher or lower

Time: O(LogN); Space: O(1); easy

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

  • -1 : My number is lower

  • 1 : My number is higher

  • 0 : Congrats! You got it!

Example 1:

Input: n = 10 (pick = 6)

Output: 6

1. Binary Search [O(LogN), O(1)]

[14]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    my_number = 6

    def guess(self, n):
        if self.my_number == n:
            return 0
        elif self.my_number > n:
            return 1
        else:
            return -1

    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n

        while left <= right:
            mid = left + (right - left) // 2
            if self.guess(mid) <= 0:
                right = mid - 1
            else:
                left = mid + 1

        return left

[15]:

s = Solution1()

n = 10    # pick = 6
assert s.guessNumber(n) == 6

# n = 10  # pick = 4
# assert s.guessNumber(n) == 4